package main

func longestValidParentheses(s string) int {
	mem := make([]int, len(s))
	stack := make([]int, 0, len(s))
	for i, c := range s {
		if c == '(' {
			stack = append(stack, i)
		} else if c == ')' {
			if len(stack) == 0 {
				mem[i] = 1
			} else {
				stack = stack[0 : len(stack)-1]
			}
		}
	}
	for len(stack) > 0 {
		top := stack[len(stack)-1]
		mem[top] = 1
		stack = stack[0 : len(stack)-1]
	}
	ans := 0
	size := 0
	for _, v := range mem {
		if v == 1 {
			size = 0
		} else {
			size++
			if size > ans {
				ans = size
			}
		}
	}
	return ans
}

func main() {
	ans := longestValidParentheses("(()")
	println(ans)
	ans = longestValidParentheses("")
	println(ans)
	ans = longestValidParentheses(")()())")
	println(ans)
}
